package Datas_Structure.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树（最优二叉树）
 *   它是n个带权叶子节点构成的所有二叉树中，带权路径长度（WPL）最小的二叉树
 *   将一列数先进行排序，再将其中最小的两个数相加，直到结束
 *
 */
public class HeFuManTree implements Comparable<HeFuManTree>{
    //权值
    int value;
    HeFuManTree lNode;
    HeFuManTree rNode;

    public HeFuManTree(int value) {
        this.value = value;
    }
     //实现自然排序接口的方法
    @Override
    public int compareTo(HeFuManTree o) {
        return -(this.value-o.value);
    }

    @Override
    public String toString() {
        return "HeFuManTree{" +
                "value=" + value +
                '}';
    }
}

class HeFuManTreeTest{
    public static void main(String[] args) {
        int[] data = {3,5,7,8,29,11,23,14};
        System.out.println(HuffmanTest(data));
    }
    //创建赫夫曼数
    public static HeFuManTree HuffmanTest(int[] arr){
       //先创建一个个二叉数
        List<HeFuManTree> list = new ArrayList<>();
        for (int value : arr) {
            list.add(new HeFuManTree(value));
        }
        //循环
        while (list.size() > 1){
            //排序
            Collections.sort(list);
            //取出权值最小的两个二叉树
            //最小
            HeFuManTree l = list.get(list.size()-1);
            //次小
            HeFuManTree r = list.get(list.size()-2);
            //算出权值
            HeFuManTree newNode = new HeFuManTree(l.value+r.value);
            //删除最小和次小
            list.remove(l);
            list.remove(r);
            //吧新节点放入列表
            list.add(newNode);
        }
        return list.get(0);
    }
}